A good answer might be:

Think dynamically, in terms of parameters and activations

Dynamic Thinking

Say that a main() program has called Fib(5). The diagram shows the activations, their parameters (in blue), and their return values (in red). Pick an activation and study how the activations below it correspond to the code.

The diagram labeled All Activations shows how each activation except for the base cases are supported by other activations. However, this diagram does not show the sequence of activations and returns. Click on the diagram a few time to see this sequence.

The diagram that shows all the activations that happen looks like an up-side-down tree, not like a single chain.

However, at any time in the execution of Fib() the activations that have not yet finished their computation (because they are waiting for a value) form a single chain. There is never more than one activation chain. The activation chain bends left and right, but there is always a single successor and a single predecessor for each link (except for the first activation and for the base cases.)

Click on the diagram a few more times to see this. The activations shows as dotted circles have finished their computation and are now "history". They are no longer on the activation chain.



QUESTION 18:

For Fib(5), 9 activations occur. Examine the diagram. Do you imagine that for Fib(N) that there are many more than N activations.